package com.sheng.leetcode.year2022.month11.day18;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/11/18
 *<p>
 * 891. 子序列宽度之和<p>
 *<p>
 * 一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。<p>
 * 给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和 。<p>
 * 由于答案可能非常大，请返回对 10^9 + 7 取余 后的结果。<p>
 * 子序列 定义为从一个数组里删除一些（或者不删除）元素，但不改变剩下元素的顺序得到的数组。<p>
 * 例如，[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。<p>
 *<p>
 * 示例 1：<p>
 * 输入：nums = [2,1,3]<p>
 * 输出：6<p>
 * 解释：子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。<p>
 * 相应的宽度是 0, 0, 0, 1, 1, 2, 2 。<p>
 * 宽度之和是 6 。<p>
 *<p>
 * 示例 2：<p>
 * 输入：nums = [2]<p>
 * 输出：0<p>
 *<p>
 * 提示：<p>
 * 1 <= nums.length <= 10^5<p>
 * 1 <= nums[i] <= 10^5<p>
 */
public class LeetCode0891 {

    @Test
    public void test01() {
        int[] nums = {2,1,3};
//        int[] nums = {2};
        System.out.println(new Solution().sumSubseqWidths(nums));
    }
}
class Solution {
    public int sumSubseqWidths(int[] nums) {
        /**
         * 结果取余 1000000007
         */
        Arrays.sort(nums);
        long ans = 0;
        int MOD = 1000000007;
        long x = nums[0], y = 2;
        for (int i = 1; i < nums.length; i++) {
            ans = (ans + nums[i] * (y - 1) - x) % MOD;
            x = (x * 2 + nums[i]) % MOD;
            y = y * 2 % MOD;
        }
        return (int) ((ans + MOD) % MOD);
    }
}

// 获取全部子串
//class Solution {
//    public int sumSubseqWidths(int[] nums) {
//        /**
//         * 结果取余 1000000007
//         */
//        int length = nums.length;
//        // 二进制的可能情况数量为1向左移动数组长度位数，为什么呢?因为总共是3位
//        // 每一个存在不存在两种可能 所以就是2的4次方种情况
//        int end = 1 << length;
//        //标记
//        int mark = 0;
//        //打印出每一种情况的子序列
//        for (mark = 0; mark < end; mark++) {
//            boolean isNUll = true;
//            //遍历都不存在就是空子集
//            for (int i = 0; i < length; i++) {
//                //!=0存在 =0不存在
//                if ((1 << i & mark) != 0) {
//                    isNUll = false;
//                    System.out.print(nums[i] + ",");
//                }
//            }
//            if (isNUll) {
//                System.out.print("null");
//            }
//            System.out.println();
//        }
//        return 0;
//    }
//}
